(1) Field of Invention
The present invention relates to a graph visualization system and, more particularly, to a system for generating a graph visualization based on gravitational forces due to path distance and betweenness centrality.
(2) Description of Related Art
Graph visualization is a common problem, for instance in vehicular networks, computer networks, and relational data (such as disease transmission, social networks, and graphs of citations between authors). Given such a network, understanding it is partly accomplished through visualization techniques. However, graph visualization can be a difficult problem in which a graph (or network) is the input to the algorithm, and the output is a “reasonable” realization of that graph in two dimensions. Several force-directed approaches have attempted to resolve the graph visualization problem.
For example, the work of Peter Eades in “A heuristic for graph drawing,” Congressus Numerantium, 42:149-160 (1984), was the first force-directed algorithm for graph drawing described in the literature. The work of Eades places springs (attractive force) between adjacent vertices, and a general repulsive force between all nonadjacent vertices. His algorithm does not place explicit attractive forces between vertices that are a graph distance of two or more apart, nor does he consider centrality as a metric.
Other researchers, Fruchterman, T. M. J., and Reingold, E. M., in “Graph Drawing by Force-Directed Placement.” Software: Practice and Experience, 21(11), (1991), describe a widely-adopted force-directed algorithm. The process described by Fruchterman et al. uses a spring-based model, treating edges within the graph as springs and applying Hooke's law, and treating vertices as electrons and applying Coulomb's law. These competing attractive and repelling forces are iterated, until the graph reaches a minimal energy, which is hopefully aesthetically pleasing.
In yet other work, Y. F. Hu describes, in “Efficient and high quality force-directed graph drawing,” The Mathematica Journal, 10 (37-71), (2005), a widely-used force-directed algorithm that relies upon a standard spring model with electrical charge-based repulsion. However, as was the case above, the work of Hu does not place explicit attractive forces between vertices that are a graph distance of two or more apart, nor does it consider centrality as a metric. Further, the model is dependent on a spring model.
Thus, a continuing need exists for system for generating a graph visualization that replaces the springs and electrons with gravitating particles, as well as introducing the notion of betweenness centrality to further guide the graph's evolution in time.